package com.sicheng.lc.lc笔试.美团篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/20 11:40
 */
public class 有点像编辑距离 {
    /**
     * 小团生日收到妈妈送的两个一模一样的数列作为礼物！他很开心的把玩，
     * 不过不小心没拿稳将数列摔坏了！现在他手上的两个数列分别为A和B，长度分别为n和m。
     * 小团很想再次让这两个数列变得一样。他现在能做两种操作，操作一是将一个选定数列中的某一个数a改成数b，
     * 这会花费|b-a|的时间，操作二是选择一个数列中某个数a，将它从数列中丢掉，花费|a|的时间。
     * 小团想知道，他最少能以多少时间将这两个数列变得再次相同！
     * <p>
     * <p>
     * <p>
     * 输入描述
     * 第一行两个空格隔开的正整数n和m，分别表示数列A和B的长度。
     * <p>
     * 接下来一行n个整数，分别为A1 A2...An
     * <p>
     * 接下来一行m个整数，分别为B1 B2...Bm
     * <p>
     * 对于所有数据，1≤n,m≤2000， |Ai|,|Bi|≤10000
     * <p>
     * 输出描述
     * 输出一行一个整数，表示最少花费时间，来使得两个数列相同。
     * <p>
     * <p>
     * 样例输入
     * 1 1
     * -9821
     * 7742
     * 样例输出
     * 17563
     * <p>
     * 提示
     * 可以选择两次第二种操作，消除数列A的第一个数和数列B的第一个数，需要花费9821+7742=17563的时间
     * <p>
     * 也可以选择一次第一种操作，将数列A的第一个数改成数列B的第一个数，也是需要花费9821+7742=17563的时间
     * <p>
     * 所以答案为17563
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] a = new int[n];
        int[] b = new int[m];

        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < b.length; i++) {
            b[i] = sc.nextInt();
        }

        int[][] dp = new int[n + 1][m + 1];
        for (int j = 1; j <= m; j++) {
            dp[0][j] += dp[0][j - 1] + Math.abs(b[j - 1]);
        }
        for (int i = 1; i <= m; i++) {
            dp[i][0] += dp[i - 1][0] + Math.abs(a[i - 1]);
        }

        for (int i = 1; i <= n; i++) {
            int x = a[i - 1];
            for (int j = 1; j <= m; j++) {
                int y = b[i - 1];
                if (x == y)
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = min(
                            dp[i - 1][j] + Math.abs(x),
                            dp[i - 1][j - 1] + Math.abs(x - y),
                            dp[i][j - 1] + Math.abs(y)
                    );
                }
            }
        }
        System.out.println(dp[n][m]);
    }

    static int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }
}
